// 实现findLastIndex 返回有序数组中最后一次出现位置的索引

// findLastIndex([1,2,3,3,4],3)


// 二分 是O(logn) 
function findLastIndex(arr, target) {
    const len = arr.length;
    let left = 0;
    let right = len - 1;

    while (true) {
        // 有序是前提
        if (arr[left] > target || arr[right] < target) return;

        //  通过middle 来缩小范围 target 与左右比较 修改right 的只
        let middle = Math.floor((right - left) / 2 + left)
        if (arr[middle] <= target) {
            left = middle
        } else {
            right = middle
        }


        // 夹到最小
        if (left + 1 === right && arr[right] === target) {
            return right
        }
        if (left + 1 === right && arr[left] == target) {
            return left
        }
    }

}

console.log(findLastIndex([1,2,3,3,3,4],4))


// map 是O(n)